package parallel.project.solver;

import java.awt.Point;
import java.awt.Rectangle;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;

import parallel.project.framework.Mazemap;
import parallel.project.graph.Edge;
import parallel.project.graph.Graph;
import parallel.project.graph.GraphException;
import parallel.project.graph.Node;

/**
 * A slave working for converting a maze, which is probably a portion
 * of a larger maze, into a {@link Graph} representation, where the
 * {@link Node}s are branching locations, and the {@link Edge}s are the
 * paths between them, weighted with the number of locations that must
 * be traversed to get from one to another.  The {@link Graph} is
 * optimized so that not all branch locations are {@link Node}s, but
 * only meaningful ones (i.e. if there is a branch to a dead end, that
 * link will not be in the {@link Graph}, which may mean that whole 
 * branching location may not be a {@link Node} in the {@link Graph},
 * if that was there were only 2 branches from that location).
 * <br><br>
 * The {@link Graph} is created by going through the maze grid and
 * creating a {@link Node} at each open passage location.  This
 * {@link Node} is connected to all the existing {@link Node}s
 * immediately around this location.  After the whole grid is gone
 * through, the graph is pruned to remove all {@link Node}s with 
 * only 1 or 2 edges.  This removes all the intermediate
 * {@link Node}s between branch locations, except for boundary and
 * the start and end {@link Node}s.
 * 
 * Copyright 2011
 * @author Adam Clayton
 * @author Larry Walters
 */
public class MazeToGraphSlave implements SolverSlave 
{
	/** The name of this slave among the other slaves */
	protected String slaveName;
	
	/** The master who is over this slave */
	protected SolverMaster master;
	
	/** The maze this slave is operating on */
	protected Mazemap maze;
	
	/** Flag to indicate whether this slave should be operating or
	 * not, in which case it should not be active */
	protected boolean operate;
	
	/** The {@link Graph} this slave is creating */
	protected Graph graph;
	
	/** The last {@link Node} the slave was at */
	protected Node lastVisited;
	
	/** The {@link Edge} locations being compiled */
	protected List<Point> currentEdgePoints;
	
	/** Time interval (in ms) to sleep between operations */
	protected long sleepTime;
	
	/** Indicates that this slave is dealing with the last maze chunk 
	 * in the global maze */
	protected boolean isLastMazeChunk;
	
	/**
	 * Creates a new slave with the given name, which is overseen by
	 * the given master.  It will convert the given maze into a graph
	 * and when it is done, notify the master by giving it the graph
	 * and raising a 
	 * {@link SlaveNotificationEvent.EventType}.GRAPH_COMPLETED event.
	 * If the given sleep time is > 0, it will sleep for that amount of
	 * time every time it deals with an open passage.
	 * 
	 * @param name
	 * 		The unique name of the slave, among all other slaves
	 * @param master
	 * 		The master overseeing this slave
	 * @param maze
	 * 		The maze to convert to a {@link Graph}
	 * @param sleep
	 * 		The number of milliseconds to sleep inbetween the dealing
	 * 		with open passages
	 */
	public MazeToGraphSlave(String name, SolverMaster master, 
		Mazemap maze, long sleep)
	{
		this.slaveName = name;
		this.master = master;
		this.maze = maze;
		this.operate = false;
		this.graph = new Graph();
		this.lastVisited = null;
		this.currentEdgePoints = null;
		this.sleepTime = sleep;
		this.isLastMazeChunk = false;
//		System.out.println("Slave " + this.slaveName + " created");
	}
	
	@Override
	public void run() 
	{
		this.initialize();
//		System.out.println("Slave " + this.slaveName + " started");
		double totalCells = this.maze.getWidth() * this.maze.getHeight();
		double cellCount = 0;
		// go through all the maze and add a node for every location
		// that is an open passage, connecting it to every adjacent
		// node
		for (int w = 0; w < this.maze.getWidth(); w++)
		{
			for (int h = 0; h < this.maze.getHeight(); h++)
			{
				// check if should stop
				if (!this.operate)
					return;
//				// for determining percent done
//				cellCount++;
//				double percent = ((cellCount / totalCells) * 100);
//				if (percent % 10 == 0)
//				{
//					System.out.print(this.slaveName + ":" + percent +
//						"%(" + cellCount + ")...");
//					if (percent % 20 == 0)
//						System.out.print("\n");
//				}
				Point loc = new Point(w,h);
				// if this is an open passage 
				if (this.maze.isPassage(w,h))
				{
					// get all the nodes around this one, try all 4
					// locations, but there really will be only 2 since
					// going across and down the 2D array, but oh well
					List<Node> connectTo = 
						this.getSurroundingNodes(loc);
					// make a list of the same size all with weight
					// 1, since connections to these nodes are all
					// 1 distance away
					List<Double> weights = new ArrayList<Double>();
					for (int i = 0; i < connectTo.size(); i++)
						weights.add(1.0);
					// there are no locations of the edges, since
					// they are just 1 tile distance
					// add the node to the graph
					try
					{	
						this.graph.addNode(
							this.makeName(loc),this.localToGlobal(loc),
							connectTo,weights,null);
					} catch (GraphException e)
					{}
					// if there is some sleep time indicated, do that, 
					// only sleep when dealing with a passage cause
					// other methods might only be going along a path,
					// and so to make this somewhat comparable, don't
					// count in locations can't get to
					if (this.sleepTime > 0)
					{
						try {Thread.sleep(this.sleepTime);} 
						catch (InterruptedException ie) {}
					}
				}
			}
		}
		// check if should stop
		if (!this.operate)
			return;
//		try {this.graph.toDot(this.slaveName + "_maze1.dot");}
//		catch (IOException ioe) {}
//		System.out.println("\nSlave " + this.slaveName + " pruning");
		// convert maze bounds to global
		Rectangle bounds = this.maze.getBounds();
		bounds.x = this.maze.getStartingColumn();
		// if this is the thread was the last chunk of the maze, then 
		// change the bounds to be outside the valid maze range, so that
		// all nodes on the right side of the maze can be included in 
		// the pruning, whereas normally they would be excluded cause 
		// they are on the right boundary
		if (this.isLastMazeChunk)
			bounds.width++;
		// prune the graph, thus connecting all the nodes that are
		// just along a passage between branching points, and 
		// possibly even those as well.
		try {this.graph.prune(bounds);}
		catch (GraphException ge) {ge.printStackTrace();}
//		try {this.graph.toDot(this.slaveName + "_maze2.dot");}
//		catch (IOException ioe) {}
		// check if should stop
		if (!this.operate)
			return;
		// give this maze to the master so it can combine it with the
		// other slave mazes
		this.fireNotification(
			SlaveNotificationEvent.graphMadeEvent(this,this.graph,null));
	}
	
	/**
	 * Returns a list of the {@link Node}s immediately around the given
	 * local location.  Thus, there are a maximum of 4 possible
	 * {@link Node}s returned (above, left, right, below).
	 * 
	 * @param currentLocalLocation
	 * 		The location around which to get the {@link Node}s
	 * 
	 * @return
	 * 		List of {@link Node}s around this location in the graph,
	 * 		not including any {@link Node} at this location itself, if
	 * 		it exists
	 */
	protected List<Node> getSurroundingNodes(Point currentLocalLocation)
	{
		// get current location
		int x = currentLocalLocation.x;
		int y = currentLocalLocation.y;
		// get all the nodes around this one and put them in the list
		// to return, if they actually exist
		List<Node> nodes = new ArrayList<Node>();
		Node above = 
			this.graph.findNode(this.makeName(new Point(x,y-1)));
		if (above != null)
			nodes.add(above);
		Node left = 
			this.graph.findNode(this.makeName(new Point(x-1,y)));
		if (left != null)
			nodes.add(left);
		Node right = 
			this.graph.findNode(this.makeName(new Point(x+1,y)));
		if (right != null)
			nodes.add(right);
		Node below = 
			this.graph.findNode(this.makeName(new Point(x,y+1)));
		if (below != null)
			nodes.add(below);
		// return nodes
		return nodes;
	}
	
	/**
	 * Sets up this slave, by adding to the {@link Graph} the start and
	 * end points of the maze and setting the operating flag on.  Also
	 * initializes the list holding locations seen along the current
	 * {@link Edge} to be empty and adds a single {@link Node} to the
	 * {@link Graph} at the start location.
	 */
	protected void initialize()
	{
		try
		{
			this.operate = true;
			// set the start and end points for the graph
			if (this.maze.getStart() != null)
			{
				this.graph.addStartPoint(
					this.localToGlobal(this.maze.getStart()));
			}
			if (this.maze.getEnd() != null)
			{
				this.graph.addEndPoint(
					this.localToGlobal(this.maze.getEnd()));
			}
//			System.out.println(this.slaveName + " " + this.graph.getAllStartPoints().size());
			// current location of the slave, at first it's the start 
			// point
			Point current = this.maze.getStart();
			// make a node for this starting location, and make it the
			// last one visited
			Point startLoc = this.localToGlobal(current);
			this.lastVisited = this.graph.addNode(
				this.makeName(current),startLoc,null,null,null);
			// initialize the list of edge points
			this.currentEdgePoints = new ArrayList<Point>();
		} catch (Exception e)
		{}
	}
	
	/**
	 * Makes the name for a {@link Node} using the local point given,
	 * which is converted to the global point where the {@link Node} 
	 * will be located.
	 * 
	 * @param localLocation
	 * 		The local location of the {@link Node}
	 * @return
	 * 		The name for the {@link Node}
	 */
	protected String makeName(Point localLocation)
	{
		Point globalLocation = this.localToGlobal(localLocation);
		return this.slaveName + "_" + globalLocation.x + "_" +
			globalLocation.y + "_";
	}
	
	/**
	 * Converts the given point in local coordinates to the 
	 * corresponding point in global coordinates.
	 * 
	 * @param localLocation
	 * 		Local point
	 * @return
	 * 		Equivalent global point
	 */
	protected Point localToGlobal(Point localLocation)
	{
		int globalX = localLocation.x + this.maze.getStartingColumn();
		return new Point(globalX,localLocation.y);
	}
	
	@Override
	public void fireNotification(SlaveNotificationEvent e) 
	{
		this.master.slaveNotifying(e);
	}

	@Override
	public void stop() 
	{
//		System.out.println("Slave " + this.slaveName + " stopping");
		this.operate = false;
	}
	
	/**
	 * Returns the unique name of this slave among the other slaves
	 * 
	 * @return
	 * 		The name of this slave
	 */
	public String getName()
	{
		return this.slaveName;
	}

	/**
	 * Returns the maze this slave is/was/is going to be, operating on.
	 * 
	 * @return
	 * 		This slave's maze
	 */
	public Mazemap getMaze()
	{
		return this.maze;
	}
	
	/**
	 * Indicates that this slave is operating on the last maze chunk of
	 * the global maze; used so slave can know if it's the last one and
	 * change the bounds used for pruning so that all nodes on the last
	 * column can be pruned, unless they are the end point.
	 * 
	 * @param lastSlave
	 * 		Whether this slave is dealing with the last maze chunk of
	 * 		not
	 */
	public void setIsLastSlave(boolean lastSlave)
	{
		this.isLastMazeChunk = lastSlave;
	}
}
